The present invention is related to image compression and video coding, in particular to variable length coding of an ordered series of quantized transform coefficients of a transform of a block of image data.
Common transform coding methods, such as JPEG, MPEG1, MPEG2, ITU-T-261, etc., include variable length coding as follows. For motion video, an image is divided into blocks, e.g., 8 by 8 or 16 by 16 blocks. Each image is classified as interframe or intraframe. Interframe images are typically post motion compensation. The blocks of the image are transformed and the transform coefficients are quantized. The quantized transform coefficients are then coded along a specified path according to a variable length coding method such that more likely-to-occur coefficient amplitude values or sequences of coefficient amplitude values are encoded by longer codeword than less likely-to-occur coefficient or coefficient sequences.
Two-dimensional variable length coding (2D-VLC) according to a 2D-VLC table is commonly used. In traditional 2D-VLC, statistics are collected or assumed of events that include a run of consecutive zero-valued coefficients followed by a single non-zero amplitude coefficient that follows the run length. The ordering of the series of quantized transform coefficients is along a pre-selected path, e.g., a zig-zag path, in the two-dimensional path of the transform. Thus, in a typical implementation, a two-dimensional table consisting of the ending amplitude and the run-length of the preceding consecutive zero-valued coefficients is constructed and variable length codes, such as optimal Huffman codes or arithmetic codes, are assigned according to the assumed or measured statistics to form the 2D-VLC table for the subsequent encoding process. Shorter code lengths are used for the more likely-to-occur, e.g., more frequently occurring events. Interframe and intraframe images typically have different 2D-VLC tables. The DC component is typically separately encoded. Furthermore, the 2D-VLC table may be truncated so that the least frequently occurring events use an escape code followed by a fixed length code. A special “EOB” code is used to indicate the end of the block when all remaining coefficients are zero.
Because of the widespread use of image coding, many patents have been issued on different forms of VLC. U.S. Pat. No. 4,698,672 issued Oct. 6, 1987 to Wen-hsiung Chen, one of the inventors of the present invention, for example, described one form of a two-dimensional variable length coding method.
In coding, there is likely to be a region in the lower frequencies in which the quantized non-zero coefficients are likely to form clusters, there is also likely to be another, high-frequency region where the non-zero-valued coefficients are likely to be scattered amongst zero-valued coefficients. With these observation in mind, the Basic Hybrid VLC Method of above-mentioned incorporated by reference U.S. patent application Ser. No. 10/869,229 to inventors Chen et al. was developed to encode the position and amplitude of quantized transform coefficients separately and takes advantage of the nature of the distribution of the transform coefficients in the low frequency and high frequency regions. U.S. patent application Ser. No. 10/869,229 is the parent to the present invention. The Basic Hybrid VLC Method includes establishing a breakpoint along the path to define two regions, e.g., a low frequency region and a high frequency region. A first-region coding method is used to encode the quantized coefficients in the low-frequency region, and a second-region coding method is used to encode the coefficients in the second region. In general, the first region coding method includes a method to identify and encode the relative positions and runlength of clusters of non-zero-valued coefficients in the first region, and any intervening runs of zero-valued coefficients in the first region, and a method to encode the amplitudes of the non-zero-valued coefficients in the clusters. The encoding methods further include encoding the signs of the coefficients.
In the Basic Hybrid VLC Method, the positions representing the clusters of non-zero-valued coefficients and the intervening runs of zero-valued coefficients in the low frequency region are coded using two independent one-dimensional variable length coding schemes. The position representing the runs of zero-valued coefficients terminating with a single non-zero coefficient (including the run of zero) in the high frequency region is coded using a third variable length coding scheme. Following the coding of positions, a separate variable length coding is then used to code the amplitude of each non-zero-valued coefficient.
The Extended Hybrid VLC Method of incorporated by reference U.S. patent application Ser. No. 10/898,654 provides an alternative coding method for the high frequency region by taking advantage of the very few amplitude values in the high frequency region, especially, for example, for low bit rate and interframe applications.
An observation was made that an improvement in coding efficiency can further be achieved by pairing the consecutive non-zero-valued coefficients and zero-valued coefficients as a pair and applying a single two-dimensional table to code the pair to jointly encode the relative position and runlength of the cluster of non-zero-valued coefficients and the runlength of any preceding run of zero-valued coefficients in the first region. With this observation, the 2-D Non-Zero/Zero Cluster Coding Method of above-mentioned incorporated by reference U.S. patent application Ser. No. 10/922,508 was introduced to improve the coding efficiency, for example for the low frequency region, and in other embodiments for more than the low frequency region.
The Basic Multi-Dimensional Amplitude Coding Method of above-mentioned incorporated by reference U.S. patent application Ser. No. 10/922,507 and the Multi-Table Amplitude Coding Method of above-mentioned incorporated by reference U.S. patent application Ser. No. 11/069,622 introduce a method of encoding the amplitudes of the non-zero coefficients in the clusters of the first region to further improve the coding efficiency.
The Joint Position and Amplitude Coding Method of above-mentioned incorporated by reference U.S. patent application Ser. No. 11/069,621 describes further improving the encoding of the coefficients in the first region by jointly encoding the relative positions and runlengths of the non-zero-valued coefficients in the clusters of non-zero coefficients and the runlength of any intervening zero-valued coefficients with the amplitudes of the non-zero valued coefficients in the cluster.
In each of these methods, a breakpoint is defined as the boundary between the low frequency and high frequency regions. The optimal breakpoint within the frequency spectrum of the transform used in the encoding varies from block to block and picture to picture. Pre-defined breakpoints may be used by pre-determining typical breakpoints by running experiments collecting statistics on a set of typical block coefficients. Typically, different breakpoints are determined for high resolution or high quality still image coding vs. low resolution or low quality still image coding; intraframe coding vs. interframe coding; high bit rate coding methods vs. low bit rate coding methods; DCT-based transform coding methods vs. non-DCT transform coding methods; and so forth.
Although a predetermined breakpoint can provide a satisfactory coding performance it is by no means optimum. The results of various experiments indicated that the performance of a hybrid coder can further be improved by using an optimal breakpoint. The improvement can be as large as 25% of the improvement that has been achieved using a pre-determined breakpoint.
Thus there is a need in the art for a method to determine the optimal or near optimal breakpoint for the purpose of defining a first (low-frequency) region and a second (high frequency) region for hybrid coding according to one or another of the above-mentioned hybrid coding methods described in the patent application of the RELATED PATENT APPLICATIONS section.
One method to find the optimal breakpoint, denoted y by N herein, is to conduct exhaustive search over all possible breakpoints, that is, for example, to encode the picture 63 times for an 8×8 block transform, trying different breakpoints, i.e., trying N=1, 2, . . . , 63. Comparing the length of the resulting codewords for the block provides the best N and also the codewords for such an optimal N. Such an approach is very time consuming, and thus not likely to be practical.
Thus there is a need for a more efficient method to determine the optimal or near optimal breakpoint.